---
title: "Java算法中的栈"
created: 2025-12-18
---
# Java算法中的栈

Deque（双端队列）在 Java 中，它同时承担了 C++ 中 std::stack 和 std::queue 的角色。

不要使用java中的Stack 类（它是旧 vector 实现的，同步且慢），使用 Deque 接口的实现类 ArrayDeque。

以下是 Deque 的核心 API 整理，按使用场景分类：

### 1. 初始化

```
// 必须引入包
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.LinkedList;

// 写法 1：最常用（基于数组，性能好，类似 C++ vector）
Deque<Integer> stack = new ArrayDeque<>();

// 写法 2：基于链表（如果需要频繁在中间插入删除，或者作为链表使用）
Deque<Integer> queue = new LinkedList<>();
```

### 2. 当作 栈 (Stack) 使用 (LIFO)

对应 C++ 的 std::stack。

操作都在头部（Head）进行。

| 操作 | 方法名 | 描述 | 遇到空时的行为 |
| --- | --- | --- | --- |
| 入栈 | push(E e) | 添加元素到栈顶 | 抛异常 (如果容量满) |
| 出栈 | pop() | 移除并返回栈顶元素 | 抛异常 (NoSuchElementException) |
| 查看 | peek() | 返回栈顶元素但不移除 | 返回 null |

> 注意：Java 的 pop() 会抛异常，所以通常先判断 isEmpty()。或者使用 poll() (返回 null)，但在 Stack 语义下大家习惯用 pop()。

---

### 3. 当作 队列 (Queue) 使用 (FIFO)

对应 C++ 的 std::queue。

队尾（Tail）进，队头（Head）出。

| 操作 | 方法名 | 描述 | 遇到空时的行为 |
| --- | --- | --- | --- |
| 入队 | offer(E e) | 添加元素到队尾 | 返回 false (比 add 安全) |
| 出队 | poll() | 移除并返回队头元素 | 返回 null (比 remove 安全) |
| 查看 | peek() | 返回队头元素但不移除 | 返回 null |

---

### 4. 当作 双端队列 (Deque) 使用

对应 C++ 的 std::deque。如果你需要两头操作（比如滑窗最大值问题），用这些明确的方法：

| 方向 | 插入 (Insert) | 移除 (Delete) | 查看 (Examine) |
| --- | --- | --- | --- |
| 头部 (First) | offerFirst(e) / addFirst(e) | pollFirst() / removeFirst() | peekFirst() / getFirst() |
| 尾部 (Last) | offerLast(e) / addLast(e) | pollLast() / removeLast() | peekLast() / getLast() |

> 记忆技巧：
>
> - offer/poll/peek 是不抛异常的版本（返回 false/null）。
> - add/remove/get 是抛异常的版本。
> - 刷题时建议用 offer/poll/peek 防止 Crash。

### 5. 常用通用方法

```
Deque<Integer> dq = new ArrayDeque<>();

dq.isEmpty();   // 判空，相当于 C++ empty()
dq.size();      // 大小，相当于 C++ size()
dq.contains(x); // 是否包含，O(N) 复杂度
dq.clear();     // 清空
```

### 6. 遍历与输出

ArrayDeque 的迭代器是从 Head (栈顶/队头) 到 Tail (栈底/队尾) 的。

假设按顺序 Push 了：1, 2, 3。

栈结构是：[3, 2, 1] (3 是栈顶)。

方式 A：普通的 for-each (从头到尾)

```java
// 栈顶 -> 栈底
for (Integer i : stack) {
    System.out.print(i);
}
// 输出: 321
```

方式 B：转为 String 输出 (正序需求)

如果你想恢复成存入的顺序 123，有三种办法：

1. 从尾部取 (推荐)：

   ```
   while (!stack.isEmpty()) {
       System.out.print(stack.pollLast()); // 移除并打印栈底元素
   }
   ```
2. 逆序迭代器：

   ```
   Iterator<Integer> it = stack.descendingIterator();
   while(it.hasNext()) {
       System.out.print(it.next());
   }
   ```
3. 转 List 再反转 (慢，不推荐)：

   ```
   List<Integer> list = new ArrayList<>(stack);
   Collections.reverse(list);
   ```

### 总结速查

| **场景** | **核心 API** |
| --- | --- |
| 模拟 Stack | push(), pop(), peek() |
| 模拟 Queue | offer(), poll(), peek() |
| 两头都要动 | offerFirst/Last, pollFirst/Last |
| 避坑 | ArrayDeque 不允许存 null，存 null 会报错。 |